1. Field of the Invention
The present invention relates generally to code generation in a data communications system, and in particular, to an apparatus and method for generating complementary turbo codes, considering the characteristics of turbo codes in a packet communications system or a general communications system that employs a retransmission scheme.
2. Description of the Related Art
In general, an ARQ (Automatic Repeat Request) system using IR (Incremental Redundancy) is classified into an HARQ (Hybrid Automatic Repeat Request) Type II system and an HARQ Type III system. The HARQ Type II system supports a code rate R higher than 1.0 at each transmission, and variably controls an amount of transmission redundancy according to a channel condition. Here, that the code rate R is higher than 1.0 means that the number of codeword symbols is less than the number of information symbols. The HARQ Type II system combines previously received redundancy with currently received redundancy to create a new low code rate codeword, and repeats this process. However, the HARQ Type III system is designed such that a code rate R of a code used at each transmission or retransmission is less than 1.0. This is to make it possible to perform decoding with only the newly received codes when many packets are missing during transmission due to a bad channel condition or detection error. When all of the codes received at code rate R can be independently decoded, the codes are referred to as “self decodable codes” (SDCs).
The HARQ Type II or HARQ Type III system using turbo codes uses quasi-complementary turbo codes (QCTCs) in order to maximize performance of code combining. FIG. 1 illustrates a block diagram of an apparatus for generating QCTCs. The QCTCs are fully described in U.S. Pat. No. 6,877,130, granted on Apr. 5, 2005 to the same assignee herein, the contents of which are hereby incorporated by reference.
Referring to FIG. 1, an encoder 301 generates coded symbols by encoding input encoder packet. The encoder 301 uses a mother code with R=1/5 or with any other code rate. A mother code is determined by the system in use. A turbo code with R=1/5 is used herein as a mother code by way of example. A demultiplexer (DEMUX) 302 groups the coded symbols received from the encoder 301 into information symbols X (303), parity symbols Y0 (313), parity symbols Y1 (323), parity symbols Y0′ (333), and parity symbols Y1′ (343), and outputs the five symbol groups to corresponding sub-block interleavers 304, 314, 324, 334 and 344, respectively. The sub-block interleavers 304, 314, 324, 334 and 344 randomly permute the sequences output from the demultiplexer 302 by sub-block interleaving, and output the permuted symbols. The codeword symbols randomized by the sub-block interleaving are applied to corresponding blocks. The interleaved coded symbols X (306) output from the first interleaver 304 are applied directly to the input of a sequence (or symbol) concatenator 307. The interleaved parity symbols Y0 and Y1 from the second and third interleavers 314 and 324 are input to a first multiplexer (MUX) 305 and the interleaved coded symbols Y0′ and Y1′ from the fourth and fifth interleavers 334 and 344 are input to a second MUX 315. The first MUX 305 multiplexes the interleaved parity symbols Y0 and Y1 and feeds the output (316) to the sequence concatenator 307. The second MUX 315 multiplexes the interleaved parity symbols Y0′ and Y1′ and feeds the output (326) to the sequence concatenator 307. That is, the coded symbols received from the encoder 301 are classified into three sub-groups of the interleaved codeword symbols output from the interleaver 304, and the parity symbols Y0 and Y1 rearranged by the first MUX 305, and the parity symbols Y0′ and Y1′ rearranged by the second MUX 315. Next, sequence (or symbol) concatenator 307 generates one symbol sequence [A:B:C] by sequentially concatenating a sub-block-interleaved information symbol sequence A, and multiplexed parity symbol sequences B and C. A concatenated sequence (or symbol) repeater 308 performs symbol repetition on the symbols from the sequence concatenator 307 according to a preset rule. A symbol puncturer (or sub-code Cij generator) 309 generates sub-codes (i.e., QCTCs) by puncturing the symbols from the concatenated sequence repeater 308 according to a preset rule. An operation of the symbol puncturer 309 will be described in detail. A sub-code generating operation by the sub-code generator 309 is disclosed in Korean Patent Application No. 2001-7357, entitled “Apparatus and Method for Generating Codes in a Communication System”, earlier filed by the applicant, the contents of which are incorporated herein by reference.
It is assumed that transmission of a sub-code starts at time k, a sub-code transmitted at time (k+h) is expressed as Cij(k+h), and the coded symbols of a mother code with R=1/5 in FIG. 1 are defined as Cm(0), Cm(1), . . . , Cm(N−1). The number, N, of the coded symbols is defined as N=L_INF×5 since the mother code rate is 1/5. Here, L_INF denotes the size of an interleaved sub-block, or the number of information symbols.
Step 1: Determining the Length of an Initial Sub-Code
For an initial transmission, one Ci0 of the first sub-codes C00, C10, C20 of available QCTCs is selected according to a given code rate and the length of the selected sub-code Ci0 is stored as a variable L_SC. The code rate or length L_SC of the sub-code is predetermined in the system according to channel environment including transmission channel condition and input data rate. The description is made in the context of three QCTCs shown in FIG. 3 for better understanding of the present invention, but the number of sub-codes is not limited.
Step 2: Selecting and Transmitting a Sub-code for Initial Transmission
After the length of a sub-code to be transmitted is determined, Cm(0), Cm(1), . . . , Cm(L_SC−1) coded symbols are selected among the coded symbols of the mother code. If L_SC exceeds N, Cm(0), Cm(1), . . . , Cm(L_SC−1) are transmitted P times and then Cm(0), Cm(1), . . . , Cm(q−1) are transmitted. Here, P and q are the quotient and remainder of L_SC/N, respectively, and P and q are calculated by L13 SC mod N. Then, the variable q is stored for the next transmission for use in detecting the position of the last symbol of the previous transmitted sub-code with respect to the block of interleaved symbols.
Step 3: Determining the Starting Position of a Sub-code for the Next Transmission and the Length of the Sub-code
For the next transmission, the code rate R_SC of a new sub-code to be transmitted is determined according to channel environment and the length L_SC of the sub-code is determined according to the determined code rate. The length L_SC and the code rate R_SC are in the relation ofL—SC=L—INF×(1/R—SC)  (1)An upper layer system transmits the sub-code length L_SC and the sub-code code rate R_SC to the symbol puncturer 309 for each transmission.
Step 4: Selecting and Transmitting a Sub-code for the Next Transmission
After the length L_SC of the sub-code to be transmitted is determined, Cm(q), Cm(q+1), . . . , Cm(q+L_SC−1) coded symbols are selected among the coded symbols of the mother code. In other words, as many symbols as the sub-code length are selected from the mother coded symbols starting with the symbol following the last symbol selected for the previous transmission. If q+L_SC exceeds N, N coded symbols starting with Cm(q) are selected recursively and transmitted P times and then the remaining q coded symbols are sequentially transmitted. Here, P and q are the quotient and remainder of (q+L13 SC)/N, respectively and P and q are calculated by (q+L_SC) mod N. Then, the variable q is stored for the next transmission for use in detecting the position of the last symbol of the previous transmitted sub-code with respect to the block of interleaved symbols. After the generated sub-code is transmitted, the procedure returns to Step 3.
A sub-code selection method for the QCTCs is illustrated in detail in a lower part of FIG. 1 by way of example. Referring to FIG. 1, a low rate sub-code with a code rate of 1/7 is initially transmitted in Case 1, and a high rate sub-code with a code rate of 4/7 is initially transmitted in Case 2. As seen from the Cases, a codeword having N codeword symbols is repeated P times, and the repeated codeword symbols are sequentially segmented in a proper size according to a length (or code rate) of the sub-code, at each transmission. In real implementation, a buffer is not used to store P codewords, but a single circular buffer is employed to store N codeword symbols, thereby making it possible to enable iterative transmission by continuous feedback. In addition, any reception buffer for storing received codewords and concatenating the stored codewords is available to a receiver as long as it can store N soft metrics.
As described above, the sub code Cij generator corresponding to the last step segments the coded symbols with R=1/5, rearranged according to a specific rule in the preceding steps, in an arbitrary length according to a sub-code code rate Rs=R_SC.
Here, if a starting point Fs for the segmentation is ‘0’, segmentation methods according to respective sub-code code rates are illustrated in FIG. 2. Referring to FIGS. 1 and 2, if a length of the sub-code to be segmented according to a code rate of the corresponding sub-code is given, the QCTC generator (of FIG. 1) segments as many codeword symbols as the corresponding length in the rearranged codeword sequence with R=1/5. Here, the segmentation is divided into two different methods. A first method is to employ a variable starting point Fs. That is, an initially transmitted sub-code starts at Fs=0, and a starting point Fs of a subsequent sub-code is determined as an (Ls+1)th symbol position from the last symbol position Ls of the preceding sub-code. In other words, all of the sub-codes are segmented such that the rearranged codewords with R=1/5 are continuously concatenated in the repeated sequence. This is defined as a sequential starting point mode (SSPM). A second method is to employ a fixed starting point Fs. That is, an initially transmitted sub-code starts at Fs=0, and the following sub-codes start at a predefined starting point Fs. Therefore, not all of the sub-codes may be sequentially concatenated in the sequence where the rearranged codewords with R=1/5 are repeated, and segmented in the form that the codeword symbols can be overlapped according to the sub-code code rate. This is defined as a fixed starting point mode (FSPM).
In application of the QCTCs, the SSPM becomes an optimal scheme in terms of maximizing decoding performance, and can maximize a code combining gain even when considering the IR However, if a code rate of the sub-code is close to 1.0, there is a probability that sub-codes other than the initial sub-code will undesirably become non self-decodable codes (NSDCs). As stated before, it is assumed that both the HARQ Type II and the HAQR Type III are available in the SSPM. If a code rate of all the transmission sub-codes is less than 1.0, the HARQ Type III is employed, whereas if a code rate of a part of the sub-codes is higher than 1.0, the HARQ Type II is employed.
That the currently proposed system employs the HARQ Type III in which a code rate of all of the sub-codes is less than 1.0 means that a receiver performs decoding by sequentially code combining all of the received sub-codes. Further, in the SSPM, a redundancy version (RV) is not exchanged between the transmitter and the receiver. This is because it is not necessary to exchange the redundancy version RV between the transmitter and the receiver in the SSPM.
However, when some sub-codes are missing in a very poor channel environment, a phenomenon of awaiting the missing sub-codes may occur in order to continuously perform code combining. In this case, therefore, self-decodable codes (SDCs) capable of independently decoding the respective sub-codes are required as in the HARQ Type III where the RV is provided. This means that an independent RV is transmitted at each sub-code transmission. In this context, the proposed scheme is the FSPM. In this case, a conventionally used 2-bit SPID (sub-packet identification) is used together with an RV indicator, and therefore, it is possible to independently transmit 4 kinds of RVs or starting points (Fs) at each sub-code transmission. Meanwhile, the FSPM cannot become an optimal scheme in terms of maximizing decoding performance, since symbol overlapping occurs. Further, the FSPM cannot maximize a code combining gain even when considering the IR.
Therefore, in the following description of the present invention, a difference between the SSPM and the FSPM will first be analyzed, and then advantages and disadvantages of the respective schemes will be analyzed. Thereafter, it will be proven that the SSPM is superior to the FSPM. Accordingly, the present invention will provide a method of enabling the FSPM to have the same performance as that of the SSPM. In particular, the present invention will show that the FSPM has a performance degradation problem due to the symbol overlapping and the symbol puncturing, and provide adaptive SPID selection schemes as a solution to the problem.